package com.example.lcode.backtrack;

import java.util.ArrayList;
import java.util.List;

public class Question113 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> re = new ArrayList<>();
        if (root == null) {
            return res;
        }
        int number = root.val;
        re.add(root.val);
        pathSum(root, number, re, targetSum, res);
        return res;
    }

    private void pathSum(TreeNode root, int number, List<Integer> re, int targetSum, List<List<Integer>> res) {
        if (number == targetSum && root.left == null && root.right == null) {
            res.add(new ArrayList<>(re));
            return;
        } else if (root.left == null && root.right == null){
            return;
        }
        for (int i = 0; i < 2; i++) {
            if (i == 0 && root.left != null) {
                re.add(root.left.val);
                pathSum(root.left, number + root.left.val, re, targetSum, res);
                re.remove(re.size() - 1);
            } else if (i == 1 && root.right != null){
                re.add(root.right.val);
                pathSum(root.right, number + root.right.val, re, targetSum, res);
                re.remove(re.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(-2);
        TreeNode treeNode1 = null;
        TreeNode treeNode2 = new TreeNode(-3);
        treeNode.left = treeNode1;
        treeNode.right = treeNode2;
        Question113 question113 = new Question113();
        List<List<Integer>> lists = question113.pathSum(treeNode, -5);
        System.out.println(lists);
    }


}
